package com.caochenlei.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BreadFirstPaths {
    private boolean[] marked;                       //索引代表顶点，值表示当前顶点是否已经被搜索
    private int[] edgeTo;                           //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
    private int s;                                  //记录有多少个顶点与顶点s相通

    public BreadFirstPaths(Graph G, int s) {        //构造广度优先搜索对象
        this.marked = new boolean[G.size()];        //初始化marked数组
        this.edgeTo = new int[G.size()];            //初始化edgeTo数组
        this.s = s;                                 //初始化起点
        bfs(G, s);                                  //使用广度优先搜索找出G图中起点为s的所有路径
    }

    private void bfs(Graph G, int v) {              //使用广度优先搜索找出G图中v顶点的所有相通顶点
        Queue<Integer> queue = new LinkedList<>();  //用来存储待搜索邻接表的点
        marked[v] = true;                           //把v顶点标识为已搜索
        queue.add(v);                               //让顶点v进入队列，待搜索
        while (!queue.isEmpty()) {                  //如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
            Integer wait = queue.poll();            //弹出一个待搜索的顶点
            for (Integer w : G.adj(wait)) {         //遍历wait顶点的邻接表
                if (!marked[w]) {                   //判断当前w顶点有没有被搜索过
                    edgeTo[w] = wait;               //到达顶点w的路径上的最后一个顶点是wait
                    marked[w] = true;               //把w顶点标识为已搜索
                    queue.add(w);                   //让顶点w进入队列，待搜索
                }
            }
        }
    }

    //判断v顶点与顶点s是否存在路径
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    //找出从起点s到顶点v的路径
    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x]) {
            path.push(x);
        }
        path.push(s);
        return path;
    }
}
